package algorithm;

import java.util.Vector;

import utilities.Global;
import utilities.MinPriorityQueue;
import graph.Configuration;
import graph.Graph;
import graph.Node;

public class Dijkstra implements Algorithm {

	// the origin Adjacency matrix
	private final int[][][] adjacencyMatrix;

	// the predecessor matrix
	private int[][] predecessorMatrix;
	
	// the grandfather who lead to the vertex matrix
	private int[][] grandfatherMatrix;
	
	// the predecessor edge side matrix
	private int[][] predecessorEdgeSideMatrix;

	// minimum priority queue
	private MinPriorityQueue minPriorityQ;
	
	// holds it to verify edges legality
	private Configuration config;
	
	private Graph graph;
	private int[] doneNodes;
	private int source;

	public Dijkstra(int columnSize, Configuration config) {
		this.graph = config.getGraph();
		this.adjacencyMatrix = graph.getEdges();
		predecessorMatrix = new int[adjacencyMatrix.length][adjacencyMatrix.length];
		grandfatherMatrix = new int[adjacencyMatrix.length][adjacencyMatrix.length];
		predecessorEdgeSideMatrix = new int[adjacencyMatrix.length][adjacencyMatrix.length];
		minPriorityQ = new MinPriorityQueue();
		this.config = config;
	}

	// The Algorithm
	public int[] run_dijkstra() {

		// initialization
		int n = this.adjacencyMatrix.length;

		// the shortest distances matrix
		doneNodes = new int[n];
		
		initializeSingleSource();

		minPriorityQ.addAll(this.adjacencyMatrix[source]);

		Node u = minPriorityQ.extractMin(graph);

		while (u.getDistance() < Global.INFINITY) {

			int uIndex = u.getId();

			// for each vertex v in adj(u)
			for (int i = 0; i < n; i++) {

				boolean success = false;
				
				//run a legacy check and, if possible, the relax function 
				int pre = predecessorMatrix[source][uIndex];
				
				if(runLegacyRelax( u, i, pre, 0, false))
						success = true;
				if(runLegacyRelax(u, i, pre, 1, false))
						success = true;
				
				/**
				 * if could not reach the vertex through the current father,
				 * search for another way to get to the vertex
				 * (- through another entry of the vertex) 
				 */
				if(!success){
					Vector<Integer> entriesToCheck = calcEntry(uIndex);
					for(int entry : entriesToCheck)
						if(entry != pre){
							runLegacyRelax( u, i, entry, 0,true);
							runLegacyRelax( u, i, entry, 1, true);
						}
				}

			}

			u = minPriorityQ.extractMin(graph);
		}

		return doneNodes;
	}
	
	/**
	 * @param num - number of function calling times
	 * @param u - node`s id
	 */
	private Vector<Integer> calcEntry(int u) {
		Vector<Integer> entriesToCheck = new Vector<Integer>();
		Vector<Integer> neighbors = config.getNeighbors(u);
		
		for(int node : neighbors)
			if(doneNodes[node] < Global.INFINITY)
				entriesToCheck.add(node);
		
		return entriesToCheck;
	}

	private boolean runLegacyRelax(Node u, int i, int pre, int edgeSide, boolean isGrand){

		if (this.adjacencyMatrix[u.getId()][i][edgeSide] == 1){
			int preEdgeSide = config.isLegal(pre, u, i, edgeSide);
			if (preEdgeSide != -1){
				relax(u.getId(), i, edgeSide, pre, isGrand, preEdgeSide);
				return true;
		}
		}
		return false;
	}

	private void initializeSingleSource() {

		for (int i = 0; i < this.adjacencyMatrix.length; i++) {
			doneNodes[i] = Global.INFINITY;
			predecessorEdgeSideMatrix[source][i] = Global.UNDEFINED;
			grandfatherMatrix[source][i] = Global.UNDEFINED;
			predecessorMatrix[source][i] = Global.UNDEFINED;
		}
		
		doneNodes[source] = 0;
		predecessorMatrix[source][source] = source;
		grandfatherMatrix[source][source] = source;

	}

	private void relax(int pre, int v, int edgeSide, int grand, boolean isGrand, int preEdgeSide) {

		if (doneNodes[v] > doneNodes[pre] + this.adjacencyMatrix[pre][v][edgeSide]) {

			if(isGrand){
				doneNodes[v] = doneNodes[grand] + this.adjacencyMatrix[grand][pre][preEdgeSide] 
				                                + this.adjacencyMatrix[pre][v][edgeSide];
				this.grandfatherMatrix[source][v] = grand;
			}
			else
				doneNodes[v] = doneNodes[pre] + this.adjacencyMatrix[pre][v][edgeSide];
			
			predecessorEdgeSideMatrix[source][v] = edgeSide;
			
			graph.getNode(v).setDistance(doneNodes[v]);
			minPriorityQ.add(graph.getNode(v));

			this.predecessorMatrix[source][v] = pre;
			
		}

	}

	@Override
	public int[][] run_all_pairs() {
		int n = this.adjacencyMatrix.length;
		int[][] allPairsMatrix = new int[n][n];

		for (int i = 0; i < n; i++) {
			setSource(i);
			allPairsMatrix[i] = run_dijkstra();
		}
		return allPairsMatrix;
	}

	private void setSource(int i) {
		source = i;
		
	}

	@Override
	public int[][] getPredecessorMatrix() {
		return this.predecessorMatrix;
	}
	
	public int[][] getGranfatherMatrix() {
		return this.grandfatherMatrix;
	}
	
	public int[][] getPredecessorEdgeSideMatrix() {
		return predecessorEdgeSideMatrix;
	}

}
